public class FindGreatestSumOfSubArray {
    // 连续子数组的最大和
    // https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int FindGreatestSumOfSubArray (int[] array) {
        // write code here
        // dp[i]表示以第i个元素为结尾的所有子数组的最大和
        int[] dp = new int[array.length];
        // 以第i个位置为结尾的结果有两种，一种是接在前面子数组的后面，一个是只有当前元素的子数组,而第i个元素之前的子数组的最大和在dp[i-1]中记录了,所以
        // dp[i] = max(dp[i-1] + array[i], array[i])
        dp[0] = array[0];
        int ret = array[0];
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}
